#include <iostream>

using namespace std;
/*
队列有头 尾 长度 已存储数量 数据
堆栈只有顶 长度 数据
*/

typedef struct _DATA_NODE
{
	int* pData;
	char* pFlag;
	int num;
}DATA_NODE;

#define STATUS int
#define TRUE 1
#define FALSE 0

DATA_NODE* malloc_node(int number)
{
	DATA_NODE* pDataNode = NULL;
	if(number == 0)
		return NULL;

	pDataNode = (DATA_NODE*)malloc(sizeof(DATA_NODE));
	memset(pDataNode, 0, sizeof(DATA_NODE));

	pDataNode->pData = (int*) malloc(sizeof(int)*number);
	if(pDataNode->pData == NULL){
		free(pDataNode);
		return NULL;
	}

	pDataNode->pFlag = (char*)malloc((number+7)>>3);
	if(pDataNode->pFlag == NULL){
		free(pDataNode->pData);
		free(pDataNode);
		return NULL;
	}

	memset(pDataNode->pData, 0, sizeof(int)*number);
	memset(pDataNode->pFlag, 0, (number+7)>>3);
	pDataNode->num = number;
	return pDataNode;
}

STATUS free_node(const DATA_NODE* pDataNode)
{
	if(pDataNode == NULL)
		return FALSE;
	free(pDataNode->pFlag);
	free(pDataNode->pData);
	free((void*)pDataNode);
	return TRUE;
}

int check_if_data_exist(const DATA_NODE* pDataNode)
{
	int number = pDataNode->num;
	char* pFlag = pDataNode->pFlag;
	unsigned char flag = 0;
	int loop = 1;

	while(loop <= number){
		flag = pFlag[((loop + 7)>>3) -1] & (0x1 <<((loop + 7)%8));   //Import!!
		if(flag != 0){
			return loop;
		}
		loop++;
	}
	return -1;
}

int* alloca_data(const DATA_NODE* pDataNode)
{
	int* pData = NULL;
	int pos;
	if(pDataNode == NULL)
		return NULL;
	if((pos = check_if_data_exist(pDataNode)) == -1)
		return NULL;

	pDataNode->pFlag[((pos+7)>>3 -1)] |= 0x1<<((pos+7)%8);    //与取或赋
	return pDataNode->pData + (pos -1);  //返回一个指向数据区域的指针
}

STATUS free_data(const DATA_NODE* pDataNode, const int* pData)
{
	int pos = 0;
	if(pDataNode == NULL || pData == NULL)
		return FALSE;

	if(pData < pDataNode->pData || pData > (pDataNode->pData + pDataNode->num))
		return FALSE;
	pos = (pData - pDataNode->pData)>>3;   //好像不应该做右移
	pDataNode->pFlag[(pos+7)>>3-1] &= ~(0x1 <<((pos+7)%8));
	return TRUE;
}

int count_free_space(const DATA_NODE* pDataNode)
{
	int count = 0;
	int loop = 1;
	char flag = 0;
	if(pDataNode == NULL)
		return 0;
	for(;loop <= pDataNode->num;loop++)
	{
		flag = pDataNode->pFlag[(loop+7)>>3-1]&(0x1<<((loop+7)%8));
		if(flag == 0){
			count ++;
		}
	}
	return count;
}




int main()
{
    cout << "Hello world!" << endl;
    return 0;
}
